﻿// 3713. 不同的子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
/*
https://www.acwing.com/problem/content/3716/

给定一个字符串 S 和一个字符串 T
，请问共有多少个 S的不同的子序列等于 T。

输入格式
第一行包含整数 Q，表示共有 Q组测试数据。

每组数据第一行包含字符串 S，第二行包含字符串 T。

输出格式
每组数据输出一行，一个结果，由于结果可能很大，
因此输出其对 1000000007取模后的值。

数据范围
1≤Q≤50
,
1≤|S|,|T|≤104

保证 T中的每个字符都是随机生成的。
字符串中只包含小写字母。

输入样例：
2
aaabbb
ab
njnunju
nju
输出样例：
9
5
*/

const int N = 10010;
const int MOD = 1000000007;
int dp[2][N];

char A[N], B[N];

int t;


void solve() {
	memset(dp, 0, sizeof dp);
	scanf("%s%s", A + 1, B + 1);
	int Alen = strlen(A + 1);
	int Blen = strlen(B + 1);
	/*if (Alen < Blen) {
		puts("0");
		return;
	}*/

	for (int i = 0; i < Alen; i++) { dp[0][i] = 1; }

	int curr = 1; int prev = 0;

	for (int i = 1; i <= Blen; i++) {
		for (int j = 1; j <= Alen; j++) {
			dp[curr][j] = dp[curr][j - 1] ;
			if (B[i] == A[j]) {
				dp[curr][j] += dp[prev][j - 1];
				dp[curr][j] %= MOD;
			}
		}
		dp[prev][0] = 0;
		swap(prev, curr);
		if (dp[prev][Alen] == 0) break;
	}

	//cout << dp[prev][Alen] << endl;
	printf("%d\n", dp[prev][Alen]);
}


int main()
{
	scanf("%d", &t);
	while (t--) {
		solve();
	}

	return 0;
}
